package com.test.daily.leetcode.y2022.m05.day0518.v01;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/18 上午 09:20
 * @version: 1.0
 */
public class Solution {
    // 找到重合次數最多的綫段
    public static class Heaper {
        int limit;
        int heapSize;
        int[] arr;

        public Heaper(int limit) {
            this.limit = limit;
            this.arr = new int[this.limit];
        }

        public void push(int value){
            if(heapSize == this.limit){
                throw new RuntimeException("is full");
            }
            arr[heapSize] = value;
            heapInsert(arr, heapSize++);
        }
        public int pop(){
            int ans = arr[0];
            swap(arr, 0, --heapSize);
            heapify(arr, heapSize, 0);
            return ans;
        }
        public void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        public void heapInsert(int[] arr, int index) {
            while (arr[index] < arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void heapify(int[] arr, int heapSize, int index) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                largest = arr[index] > arr[largest] ? index: largest;
                if(largest == index){
                    break;
                }
                swap(arr, largest, index);
                index = largest;
                left  = index * 2 + 1;
            }
        }
        public void heapSorted(){
            for (int i = arr.length - 1; i >=0 ; i--) {
                heapify(arr, heapSize, 0);
            }
            swap(arr, 0, --heapSize);
            while(heapSize > 0){
                heapify(arr, heapSize, 0);
                swap(arr, --heapSize, 0);
            }
        }

        public static int maxLines(int[][] lines){
            int ans = 0;
            int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE;
            for (int i = 0; i < lines.length; i++) {
                min = Math.min(min, lines[i][0]);
                max = Math.max(max, lines[i][1]);
            }
            for(double p = min + 0.5; p < max; p += 1){
                int count = 0;
                for(int j = 0; j < lines.length; j++){
                    if(lines[j][0] < p && lines[j][1] >p){
                        count++;
                    }
                }
                ans = Math.max(ans, count);
            }
            return ans;
        }

        public static int maxLines02(int[][] lines){
            int max = 0;
            LineClazz[] lineClazzes = new LineClazz[lines.length];
            for (int i = 0; i < lines.length; i++) {
                lineClazzes[i] = new LineClazz(lines[i][0], lines[i][1]);
            }
            Arrays.sort(lineClazzes, new LineComparator());
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for (int i = 0; i < lineClazzes.length; i++) {
                while(!pq.isEmpty() && pq.peek()<lineClazzes[i].start){
                    pq.poll();
                }
                pq.add(lineClazzes[i].end);
                max = Math.max(pq.size(), max);
            }
            return max;
        }
        public static class LineClazz{
            int start;
            int end;
            public LineClazz(int start, int end){
                this.start = start;
                this.end = end;
            }
        }
        public static class LineComparator implements Comparator<LineClazz>{
            @Override
            public int compare(LineClazz o1, LineClazz o2) {
                return o1.start - o2.start;
            }
        }

    }
}
